因为使用优惠劵就必须买这件商品,我们可以将优惠劵的关系看成一棵树。
令 表示 以 为根的子树 , 购买 件商品 , 是否使用优惠劵的最小花费。
边界条件:
注意: 是不成立的,因为使用优惠券就必须购买商品,其余设为极大值。
然后有如下转移:
最后看满足 的最大的 即可。
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
template<typename _T>
void Read( _T &x ) {
x = 0; int f = 1;
char s = getchar( );
for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
x *= f;
}
template<typename _T>
void Write( _T x ) {
if( x < 0 ) putchar('-') , x = -x;
if( x >= 10 ) Write( x / 10 );
putchar( x % 10 + '0' );
}
const int MAXN = 5000;
int n , m , fa , c[ MAXN + 5 ] , d[ MAXN + 5 ] , Size[ MAXN + 5 ];
int dp[ MAXN + 5 ][ MAXN + 5 ][ 2 ];
vector< int > Graph[ MAXN + 5 ];
void dfs( int u ) {
Size[ u ] = 1;
dp[ u ][ 0 ][ 0 ] = 0 , dp[ u ][ 1 ][ 0 ] = c[ u ];
dp[ u ][ 1 ][ 1 ] = c[ u ] - d[ u ];
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
dfs( v );
for( int j = Size[ u ] ; j >= 0 ; j -- ) //注意循环顺序,不然会超时
for( int k = 0 ; k <= Size[ v ] ; k ++ ) {
dp[ u ][ j + k ][ 0 ] = min( dp[ u ][ j + k ][ 0 ] , dp[ u ][ j ][ 0 ] + dp[ v ][ k ][ 0 ] );
dp[ u ][ j + k ][ 1 ] = min( dp[ u ][ j + k ][ 1 ] , dp[ u ][ j ][ 1 ] + min( dp[ v ][ k ][ 0 ] , dp[ v ][ k ][ 1 ] ) );
}
Size[ u ] += Size[ v ];
}
}
int main( ) {
Read( n ) , Read( m );
for( int i = 1 ; i <= n ; i ++ ) {
Read( c[ i ] ) , Read( d[ i ] );
if( i >= 2 ) {
Read( fa );
Graph[ fa ].push_back( i );
}
}
memset( dp , 0x3f , sizeof( dp ) );
dfs( 1 );
for( int i = n ; i >= 0 ; i -- )
if( dp[ 1 ][ i ][ 0 ] <= m || dp[ 1 ][ i ][ 1 ] <= m ) {
Write( i ) , putchar('\n');
return 0;
}
return 0;
}